package argo.hot100.linklist;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class CopyRandomList {

    public Node copyRandomList(Node head) {

        if (head == null) {
            return null;
        }
        List<Node> srcList = new ArrayList<>();
        List<Node> tgList = new ArrayList<>();
        Map<Node, Integer> inxMap = new HashMap<>();
        int inx = 0;
        while (head != null) {
            srcList.add(head);
            tgList.add(new Node(head.val));
            inxMap.put(head, inx++);
            head = head.next;
        }

        Node preNode = null;
        for (int i = 0; i < srcList.size(); i++) {
            Node srcNode = srcList.get(i);
            Node tgNode = tgList.get(i);

            if (i + 1 < srcList.size()) {
                tgNode.next = tgList.get(i + 1);
            } else {
                tgNode.next = null;
            }
            int random = inxMap.getOrDefault(srcNode.random, -1);
            if (random != -1) {
                tgNode.random = tgList.get(random);
            } else {
                tgNode.random = null;
            }
        }
        return tgList.get(0);
    }
}
